#include <vector>
using namespace std;

// 维护两个变量：current_sum（当前正在攒的子数组和）max_sum（目前找到的最大子数组和）初始都设为数组第一个元素
// 从数组第二个元素开始遍历
// 把当前元素加到 current_sum 上
// 要是加完后 current_sum 还不如当前元素本身大（说明之前攒的和是拖累）
// 就把 current_sum 重置为当前元素（重新从当前元素开始攒）反之就让current_sum加上当前值
// 每次处理完 current_sum 都和 max_sum 比一比，用更大的数更新 max_sum
// 遍历结束，max_sum 就是答案 全程只走一遍数组，时间复杂度 O (N)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur_sum = nums[0];
        int max_sum = nums[0];
        if(nums.size()==1)
        {
            return nums[0];
        }
        for(int i = 1;i<nums.size();i++)
        {
            int tmp = cur_sum+nums[i];
            if(tmp < nums[i])
            {
                cur_sum = nums[i];
            }
            else
            {
                cur_sum+=nums[i];
            }

            if(max_sum<cur_sum)
            {
                max_sum = cur_sum;
            }
        }

        return max_sum;

    }
};